/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author zhongfang
 *
 */
public class MagicDictionary2 {

	HashMap<Integer, ArrayList<String>> allString;

	/** Initialize your data structure here. */
	public MagicDictionary2() {

	}

	/** Build a dictionary through a list of words */
	public void buildDict(String[] dict) {
		allString = new HashMap<>();
		for (String string : dict) {
			if (!allString.containsKey(string.length())) {
				ArrayList<String> strings = new ArrayList<>();
				strings.add(string);
				allString.put(string.length(), strings);
			} else {
				allString.get(string.length()).add(string);
			}
		}
	}

	/**
	 * Returns if there is any word in the trie that equals to the given word
	 * after modifying exactly one character
	 */
	public boolean search(String word) {
		ArrayList<String> strings = allString.get(word.length());
		if (strings == null) {
			return false;
		}
		// if (strings.contains(word)) {
		// return false;
		// }
		for (String string : strings) {
			if (string.equals(word)) {
				continue;
			}
			if (findMatch(string, word)) {
				return true;
			}
		}
		return false;
	}

	private boolean findMatch(String string, String word) {// 有一个字符不同
		int sameCount = 0;
		for (int i = 0; i < string.length(); i++) {
			if (string.charAt(i) == word.charAt(i)) {
				sameCount++;
			}
		}
		return sameCount == string.length() - 1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MagicDictionary2 magicDictionary = new MagicDictionary2();
		magicDictionary.buildDict(new String[] { "hello", "hallo", "leetcode" });
		System.out.println(magicDictionary.search("hello"));
		System.out.println(magicDictionary.search("hhllo"));
		System.out.println(magicDictionary.search("hell"));
		System.out.println(magicDictionary.search("leetcoded"));
	}

}
